package Gee

import "strings"

// 前缀树

// 树节点
type node struct {
	pattern  string  // 带匹配的路由
	part     string  // 路由中的一部分
	children []*node // 子节点
	isWild   bool    // 是否精准匹配
}

//对于路由来说，最重要的当然是注册与匹配了。开发服务时，注册路由规则，映射handler；访问时，匹配路由规则，查找到对应的handler。
//Trie 树需要支持节点的插入与查询
//插入功能:递归查找每一层的节点，如果没有匹配到当前part的节点，则新建一个
// 注意:/p/:lang/doc只有在第三层节点，即doc节点，pattern才会设置为/p/:lang/doc,p和:lang节点的pattern属性皆为空
// 因此，当匹配结束时，我们可以使用n.pattern == ""来判断路由规则是否匹配成功
func (n *node) insert(pattern string, parts []string, height int) {
	if len(parts) == height { // 当路由所有的part部分都匹配上时结束, 树高 == parts的个数   (注意:height从0开始)
		n.pattern = pattern
		return
	}
	// 匹配子节点
	child := n.matchChild(parts[height]) //parts[height] 为孩子节点中待匹配的part of router
	if child == nil {                    //没有匹配到子节点,就创建一个
		// 创建的childnode只填充 part 和 isWild
		child = &node{part: parts[height], isWild: parts[height][0] == ':' || parts[height][0] == '*'}
		n.children = append(n.children, child)
	}
	child.insert(pattern, parts, height+1) // 再对child节点插入 下一个 待匹配的part of router
}

//查询功能:也是递归查询每一层的节点，退出规则是，匹配到了*，匹配失败，或者匹配到了第len(parts)层节点
func (n *node) search(parts []string, height int) *node {
	if len(parts) == height || strings.HasPrefix(n.part, "*") {
		if n.pattern == "" {
			return nil
		}
		return n
	}
	part := parts[height]
	children := n.matchChildren(part)
	for _, child := range children {
		result := child.search(parts, height+1)
		if result != nil {
			return result
		}
	}
	return nil
}

// 第一个匹配成功的节点,用于插入
func (n *node) matchChild(part string) *node {
	for _, child := range n.children {
		if child.part == part || child.isWild { // 孩子节点中的part是要进行插入的路由的一个part, 或者 孩子节点是 动态匹配
			return child
		}
	}
	return nil
}

// 所有匹配成功的节点, 用于查询匹配
func (n *node) matchChildren(part string) []*node {
	nodes := []*node{}
	for _, child := range n.children {
		if child.part == part || child.isWild { // 孩子节点中的part是要进行插入的路由的一个part, 或者 孩子节点是 动态匹配
			nodes = append(nodes, child)
		}
	}
	return nodes
}
